{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def states_set(n):\n",
    "    \"\"\"生成状态集(传教士，野人，船位置)，简记为(m,c,x)\n",
    "    x取0代表船在左岸，x在右代表船在右岸，人要从左岸到右岸\n",
    "    \"\"\"\n",
    "    \n",
    "    # 先不考虑船的位置\n",
    "    # 若右岸无教士，左岸教士为n个，左岸野人数量无所谓，状态为(n, c, x)\n",
    "    # 若左岸无教士，类似，状态为（0, c, x）\n",
    "    ssm0 = [(m,c) for m in [0,n] for c in range(n+1)]\n",
    "    # 若左右岸均有教士，为了教士安全，两侧教士数应当均不小于野人数\n",
    "    # 因此教士数只能等于野人数\n",
    "    ssm = [(c,c) for c in range(1,n)]\n",
    "    # 总状态集\n",
    "    ss = ssm+ssm0\n",
    "    \n",
    "    # 再考虑船的位置\n",
    "    # 船在左岸\n",
    "    ss0 = [(s[0],s[1],0) for s in ss]\n",
    "    # 左岸无人而船在，离谱\n",
    "    ss0.remove((0,0,0))\n",
    "    # 船在右岸\n",
    "    ss1 = [(s[0],s[1],1) for s in ss]\n",
    "    # 右岸无人而船在，离谱\n",
    "    ss1.remove((n,n,1))\n",
    "    \n",
    "    # 返回左岸的状态集和右岸的状态集\n",
    "    return ss0, ss1\n",
    "\n",
    "def movements_set(b):\n",
    "    \"\"\"生成行为集\n",
    "    船上的人数——(传教士，野人)，简记为(m,c)\n",
    "    忽略方向——因为能坐船过去就能坐船回来\n",
    "    \"\"\"\n",
    "    \n",
    "    # 船不能超载，教士不少于野人，\n",
    "    # 船上有教士\n",
    "    ms1 = [(m,c) for m in range(1,b+1) for c in range(b-m+1) if m>=c]\n",
    "    # 船上无教士\n",
    "    ms2 = [(0,c) for c in range(1,b+1)]\n",
    "    \n",
    "    # 总行为集\n",
    "    ms = ms1 + ms2\n",
    "    return ms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 输入参数：教士数（野人数），船载客量\n",
    "n, b = 3, 2 # map(int,input().split())\n",
    "\n",
    "# 生成状态集和行为集\n",
    "ss0, ss1 = states_set(n)\n",
    "ms = movements_set(b)\n",
    "\n",
    "# 初始化无向图对象和添加节点\n",
    "G = nx.Graph()\n",
    "G.add_nodes_from(ss0+ss1)\n",
    "\n",
    "# 船在左岸和右岸之间来回，具有相同x的状态之间无边，只计算x不同的状态之间的距离\n",
    "for i in ss0:\n",
    "    for j in ss1:\n",
    "        # 计算状态之间的距离，若在行为集中，就添加到图里\n",
    "        move = (i[0]-j[0], i[1]-j[1])\n",
    "        if move in ms:\n",
    "            G.add_edge(i,j)\n",
    "            nx.set_edge_attributes(G, {(i,j):{\"move\": move}})\n",
    "\n",
    "# 冻结网络\n",
    "# G = nx.freeze(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "可行的边为：\n",
      "\n",
      "(1, 1, 0) (0, 0, 1) : (1, 1)\n",
      "(1, 1, 0) (0, 1, 1) : (1, 0)\n",
      "(2, 2, 0) (1, 1, 1) : (1, 1)\n",
      "(2, 2, 0) (0, 2, 1) : (2, 0)\n",
      "(0, 1, 0) (0, 0, 1) : (0, 1)\n",
      "(0, 2, 0) (0, 0, 1) : (0, 2)\n",
      "(0, 2, 0) (0, 1, 1) : (0, 1)\n",
      "(0, 3, 0) (0, 1, 1) : (0, 2)\n",
      "(0, 3, 0) (0, 2, 1) : (0, 1)\n",
      "(3, 1, 0) (1, 1, 1) : (2, 0)\n",
      "(3, 1, 0) (3, 0, 1) : (0, 1)\n",
      "(3, 2, 0) (2, 2, 1) : (1, 0)\n",
      "(3, 2, 0) (3, 0, 1) : (0, 2)\n",
      "(3, 2, 0) (3, 1, 1) : (0, 1)\n",
      "(3, 3, 0) (2, 2, 1) : (1, 1)\n",
      "(3, 3, 0) (3, 1, 1) : (0, 2)\n",
      "(3, 3, 0) (3, 2, 1) : (0, 1)\n"
     ]
    }
   ],
   "source": [
    "e = nx.get_edge_attributes(G, \"move\")\n",
    "print(\"可行的边为：\\n\")\n",
    "for key,value in e.items():\n",
    "    print(*key, \":\", value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "可运吗？   True\n",
      "\n",
      "左岸状态依次为：\n",
      "(3, 3, 0)\n",
      "(2, 2, 1)\n",
      "(3, 2, 0)\n",
      "(3, 0, 1)\n",
      "(3, 1, 0)\n",
      "(1, 1, 1)\n",
      "(2, 2, 0)\n",
      "(0, 2, 1)\n",
      "(0, 3, 0)\n",
      "(0, 1, 1)\n",
      "(1, 1, 0)\n",
      "(0, 0, 1)\n"
     ]
    }
   ],
   "source": [
    "# 初始状态和结束状态\n",
    "ori_state = (n,n,0)\n",
    "end_state = (0,0,1)\n",
    "\n",
    "# 检查有无通路\n",
    "has_path = nx.has_path(G, ori_state, end_state)\n",
    "print(\"可运吗？  \", has_path)\n",
    "if has_path:\n",
    "    print(\"\\n左岸状态依次为：\")\n",
    "    d = dict(nx.all_pairs_shortest_path(G))\n",
    "    for node in (d[ori_state]).get(end_state,0):\n",
    "        print(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
